package no07;


/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/24 15:56
 * 重建二叉树
 * https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
 */
public class Solution {
    // 树的节点类
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    int preIndex = 0; // 用于遍历前序序列的指针

    // 根据前序和中序序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        preIndex = 0;
        return myBuildTree(preorder, inorder, 0, preorder.length-1);
    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int start, int end) {
        if (start > end) {
            return null;
        }
        int key = preorder[preIndex];
        TreeNode root = new TreeNode(key); // 创建一个新节点
        preIndex++;
        int inIndex = findIndexByInorder(inorder, key, start, end);
        // 根据区间构造左右子树
        root.left = myBuildTree(preorder, inorder, start, inIndex-1);
        root.right = myBuildTree(preorder, inorder, inIndex+1, end);
        // 返回根节点
        return root;
    }

    // 中序序列 inorder [start, end] 范围内查找 key 的 index
    private int findIndexByInorder(int[] inorder, int key, int start, int end) {
        for (int i = start; i <= end; i++) {
            if (key == inorder[i]) {
                return i;
            }
        }
        return -1;
    }
}
